#include<iostream>
#include<cstdio>
#include<cstring>
#include<assert.h>
#include<algorithm>
using namespace std;

namespace Mango
{
    class string
    {
    public:
        typedef char* iterator;
        typedef const char* const_iterator;
        string(const char* str = "")
            :_size(strlen(str)), _capacity(_size), _str(nullptr)
        {
            _str = new char[strlen(str) + 1];
            strcpy(_str, str);
        }
        string(const string& s)
            :_size(s._size), _capacity(s._capacity), _str(nullptr)
        {
            cout << "string(const string& s)" << endl;
            _str = new char[strlen(s._str) + 1];
            strcpy(_str, s._str);
        }
        void swap(string& s)
        {
            ::swap(s._size, _size);
            ::swap(s._capacity, _capacity);
            ::swap(s._str, _str);
        }
        /*
        string(const string& s)
            :_str(nullptr),_capacity(0),_size(0)
        {
            cout << "string(const string& s)" << endl;
            string tmp(s._str);
            swap(tmp);
        }
        */
        string(string&& s)
        {
            cout << "string(string&& s)" << endl;
            swap(s);
        }
        //可能有Bug，因为new可能失败，而我们已经把_str的空间释放了,所以就会导致现在_str变为野指针
        /*
        string& operator=(const string& s)
        {
            cout << "operator=(const string& s)"<<endl;
            if(this != &s)
            {
                _capacity = s._capacity;
                _size = s._size;
                delete _str;//记得要释放原空间！！！
                _str = new char[strlen(_str)+1];

                //防止\0也是有效字符,例如:_str为hel\0lo\0  如果使用strcpy,那么其拷贝遇到\0就会结束
                //所以要使用strncpy,明确指定要拷贝多少个字符，而不是使用strcpy
                strncpy(_str,s._str,_size+1); 
            }
            return *this;
        }
        */
        //解决办法：先用临时变量接收这块空间的地址,然后拷贝内容到这块空间上,然后再处理
        /*
        string& operator=(const string& s)
        {
            cout << "operator=(const string& s)"<<endl;
            if(this != &s)
            {
                char* tmp = new char[s.strlen(s._str)+1];
                if(tmp != nullptr)
                {
                    //防止\0也是有效字符,例如:_str为hel\0lo\0  如果使用strcpy,那么其拷贝遇到\0就会结束
                    //所以要使用strncpy,明确指定要拷贝多少个字符，而不是使用strcpy 并且\0也要拷贝
                    strncpy(tmp,s._str,_size+1); //内容拷贝----------------
                    
                    delete[] _str;//记得要释放原空间！！！
                    _str = tmp;
                    _capacity = s._capacity;
                    _size = s._size;
                }
                else
                {
                    cout << "new error" << endl;
                }
            }
            return *this;
        }
        */
        string& operator=(const string& s)
        {
            cout << "operator=(const string& s)" << endl;
            if (this != &s)
            {
                string tmp(s._str);
                swap(tmp);
            }
            return *this;
        }

        string& operator=(string&& s)
        {
            cout << "string& operator=(string&& s)" << endl;
            swap(s);
            return *this;
        }
        ~string()
        {
            delete[] _str;
            _str = nullptr;
            _size = _capacity = 0;
        }

        //迭代器相关函数
        iterator begin()
        {
            return _str;
        }
        iterator end()
        {
            return _str + _size;
        }
        const_iterator begin()const
        {
            return _str;
        }
        const_iterator end()const
        {
            return _str + _size;
        }

        //容量和大小相关函数
        size_t size()
        {
            return _size;
        }
        size_t capacity()
        {
            return _capacity;
        }
        void reserve(size_t n)
        {
            if (n > _capacity) //扩容
            {
                char* tmp = new char[n + 1];
                if (tmp != nullptr)
                {
                    //防止\0也是有效字符,例如:_str为hel\0lo\0  如果使用strcpy,那么其拷贝遇到\0就会结束
                    //所以要使用strncpy,明确指定要拷贝多少个字符，而不是使用strcpy 并且\0也要拷贝
                    strncpy(tmp, _str, _size + 1);
                    delete[] _str;
                    _str = tmp;
                    _capacity = n;
                }
            }
        }
        void resize(size_t n, char ch = '\0')
        {
            if (n < _size)
            {
                _str[n] = '\0';
                _size = n;
            }
            else // _capacity > n > _size || n > _capacity
            {
                if (n > _capacity)
                    reserve(n);
                //填充到n个字符
                for (int i = _size; i < n; i++)
                {
                    _str[i] = ch;
                }
                _str[n] = '\0';
                _size = n;
            }
        }
        bool empty()const
        {
            return _size == 0;
        }

        //修改字符串相关函数
        void push_back(char ch)
        {
            if (_size == _capacity)
            {
                reserve(_capacity == 0 ? 10 : _capacity * 2);
            }
            _str[_size++] = ch;
            _str[_size] = '\0';
        }
        void append(const char* str)
        {
            int len = strlen(str);
            size_t sum = len + _size;
            if (sum > _capacity)
            {
                reserve(sum);
            }
            strcpy(_str + _size, str);
            _size = sum;
        }
        string& operator+=(char ch)
        {
            push_back(ch);
            return *this;
        }
        string& operator+=(const char* str)
        {
            append(str);
            return *this;
        }
        string& insert(size_t pos, char ch)
        {
            assert(pos <= _size);
            if (_size == _capacity)
            {
                reserve(_capacity == 0 ? 10 : _capacity * 2);
            }
            char* end = _str + _size;
            _size++;
            while (end >= _str + pos)
            {
                *(end + 1) = *end;
                end--;
            }
            _str[pos] = ch;
            _str[_size] = '\0';//字符串末尾置\0
            return *this;
        }
        string& insert(size_t pos, const char* str)
        {
            assert(pos <= _size);
            int len = strlen(str);
            size_t sum = len + _size;
            if (sum > _capacity)
            {
                reserve(sum);
            }
            char* end = _str + _size;
            _size = sum;
            while (end >= _str + pos)
            {
                *(end + len) = *(end);
                end--;
            }
            strncpy(_str + pos, str, len);
            _str[_size] = '\0';//字符串末尾置\0
            return *this;
        }
        string& erase(size_t pos, size_t len = npos)
        {
            assert(pos < _size);
            int total = _size - pos;
            if (len >= total) //后面的全部删完
            {
                _str[pos] = '\0';
                _size = pos;
            }
            else
            {
                strcpy(_str + pos, _str + pos + len);
                _size -= len;
            }
            return *this;
        }
        void clear()
        {
            _size = 0;
            _str[_size] = '\0';
        }
        const char* c_str()const
        {
            return _str;
        }

        //访问字符串相关函数
        char& operator[](size_t i)
        {
            assert(i < _size);
            return _str[i];
        }
        const char& operator[](size_t i)const
        {
            assert(i < _size);
            return _str[i];
        }
        size_t find(char ch, size_t pos = 0)const
        {
            assert(pos < _size);
            for (size_t i = pos; i < _size; i++)
            {
                if (_str[i] == ch)
                    return i;
            }
            return npos;
        }
        size_t find(const char* str, size_t pos = 0)const
        {
            assert(pos < _size);
            char* res = strstr(_str + pos, str);
            if (res == NULL)
                return npos;
            else
                return res - _str;
        }
        size_t rfind(char ch, size_t pos = npos)const
        {
            Mango::string tmp(*this);
            std::reverse(tmp.begin(), tmp.end());
            if (pos >= _size)
            {
                pos = _size - 1;
            }
            pos = _size - 1 - pos;
            size_t ret = tmp.find(ch, pos);
            if (ret != npos)
            {
                return _size - 1 - ret;
            }
            else
            {
                return npos;
            }
        }
        //默认从npos位置开始找
        size_t rfind(const char* str, size_t pos = npos) const
        {
            string tmp(*this); //拷贝构造
            reverse(tmp.begin(), tmp.end()); //调用reverse逆置tmp对象的字符串
            size_t len = strlen(str); //待查找的字符串的长度
            char* arr = new char[len + 1]; //开辟arr字符串（用于拷贝str字符串）,多给一个空间是给\0的
            strcpy(arr, str); //拷贝str给arr
            reverse(arr, arr + strlen(arr));
            if (pos >= _size) //所给pos大于字符串有效长度
            {
                pos = _size - 1; //重新设置pos为字符串最后一个字符的下标
            }
            pos = _size - 1 - pos; //将pos改为镜像对称后的位置pos'
            size_t ret = tmp.find(arr, pos); //复用find函数从pos'位置开始找字符串arr
            delete[] arr; //销毁arr指向的空间,避免内存泄漏
            if (ret != npos)
                return _size - ret - len; //找到了,返回ret镜像对称后再调整的位置
            else
                return npos; //没找到,返回npos
        }
        static string to_string(int val)
        {
            bool flag = false;
            if (val < 0)
            {
                flag = true;
                val = -val;
            }
            string tmp;
            while (val)
            {
                tmp += val % 10 + '0';
                val /= 10;
            }
            if (flag)
                tmp += '-';
            ::reverse(tmp.begin(), tmp.end());
            return tmp;
        }
        //关系运算符重载函数
        bool operator>(const string& s)const
        {
            return strcmp(_str, s._str) > 0;
        }
        bool operator<(const string& s)const
        {
            return strcmp(_str, s._str) < 0;
        }
        bool operator>=(const string& s)const
        {
            return !(*this < s);
        }

        bool operator<=(const string& s)const
        {
            return !(*this > s);
        }
        bool operator==(const string& s)const
        {
            return strcmp(_str, s._str) == 0;
        }
        bool operator!=(const string& s)const
        {
            return !(*this == s);
        }

    private:
        char* _str;       //存储字符串
        size_t _size;     //记录字符串当前的有效长度
        size_t _capacity; //记录字符串当前的容量
        static const size_t npos; //静态成员变量（整型最大值）
    };
    //静态成员变量在类外初始化
    const size_t string::npos = -1;

    //<<和>>运算符重载函数
    istream& operator>>(istream& in, string& s)
    {
        s.clear();
        char ch = in.get();
        while (ch != ' ' && ch != '\n')
        {
            s += ch;
            ch = in.get();
        }
        return in;
    }
    //注意：不能 out << s.c_str(); 因为C语言形式的字符串关注的是\0，而我们这里关注的是_size
    //例如:hello\0 Mango  如果是c_str输出的是：hello  而我们想输出的是hello\0 Mango
    ostream& operator<<(ostream& out, const string& s)
    {
        for (auto& x : s)
            out << x;
        return out;
    }
    istream& getline(istream& in, string& s)
    {
        s.clear();
        char ch = in.get();
        while (ch != '\n')
        {
            s += ch;
            ch = in.get();
        }
        return in;
    }


    	//测试反向查找
	void testString8()
	{
		string tmp("Mango Hello world");
		cout << tmp.rfind('e') << endl;
		cout << tmp.rfind("He") << endl;
	}
	//测试现代写法的成员函数
	void testString1()
	{
		string s0;
		string s1("Always");
		string s2(s1);
		cout << s2.c_str() << endl;
		string s3("more than words");
		s3 = s1;
		cout << s3.c_str() << endl;
		s3 = s3;
	}
	//测试流插入流提取运算符重载
	void testString7()
	{
		//string s;
		string s("Hello Mango");
		cin >> s;
		cout << s << endl;
		// 不能以字符串形式输出,测试标准库
		string s1("more than");
		s1 += '\0';
		s1 += "words";
		cout << s1 << endl;
		cout << s1.c_str() << endl;
	}
	// 测试比较大小运算符重载
	void testString6()
	{
		string s1("abcd");
		string s2("abcd");
		cout << (s1 <= s2) << endl;
		string s3("abcd");
		string s4("abcde");
		cout << (s3 <= s4) << endl;
		string s5("abcde");
		string s6("abcd");
		cout << (s5 <= s6) << endl;
	}
	// 测试insert和erase
	void testString5()
	{
		string s(" Mango Hello");
		s.insert(0, "Lemon");
		cout << s.c_str() << endl;
		s.insert(5, '!');
		cout << s.c_str() << endl;
		s.erase(0, 7);
		cout << s.c_str() << endl;
		s.erase(6);
		cout << s.c_str() << endl;
	}
	// 测试查找
	void testString4()
	{
		string s("Mango");
		cout << s.find('m') << endl;
		cout << s.find("max") << endl;
	}
	// 测试resize
	void testString3()
	{
		string s("Mango"); // capacity - 12
		s.resize(5);
		cout << s.c_str() << endl;
		s.resize(7, '!');
		cout << s.c_str() << endl;
		s.resize(20, '~');
		cout << s.c_str() << endl;
	}
	// 测试尾插字符及字符串push_back/append,同时测试reserve
	void testString2()
	{
		string s("more than words");
		s.push_back('~');
		s.push_back(' ');
		cout << s.c_str() << endl;
		s.append("zhabuduodele");
		cout << s.c_str() << endl;
		s += '~';
		s += "yiyandingzhen";
		cout << s.c_str() << endl;
	}

}